/**
 * @author VernHe
 * @date 2021年07月23日 19:45
 * <p>
 * <p>
 * 123. 买卖股票的最佳时机 III
 * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
 * <p>
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
 * <p>
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入：prices = [3,3,5,0,0,3,1,4]
 * 输出：6
 * 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
 * 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
 * 示例 2：
 * <p>
 * 输入：prices = [1,2,3,4,5]
 * 输出：4
 * 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
 * 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
 * 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
 * 示例 3：
 * <p>
 * 输入：prices = [7,6,4,3,1]
 * 输出：0
 * 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
 * 示例 4：
 * <p>
 * 输入：prices = [1]
 * 输出：0
 */
public class Solution_0123 {
    public static void main(String[] args) {
        System.out.println(maxProfit2(new int[]{2, 1, 2, 0, 1}));
    }

    public static int maxProfit1(int[] prices) {
        // 参数判断
        if (null == prices || prices.length < 2) {
            return 0;
        }

        int len = prices.length;
        // 定义dp数组，并初始化。dp[i][j]为第i+1天到j+1天的最大利润
        int[][] dp = new int[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = 0;
        }

        for (int i = 0; i < len; i++) {
            int min = prices[i];
            for (int j = i + 1; j < len; j++) {
                if (prices[j] > min) {
                    // 涨了，利润就会在之前的基础上增加
                    dp[i][j] = Math.max(dp[i][j - 1], prices[j] - min);
                } else {
                    // 没有涨，那么最大利润和前一天一样
                    min = Math.min(min, prices[j]);
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        for (int[] rows : dp) {
            for (int num : rows) {
                System.out.printf(num + "_");
            }
            System.out.println();
        }
        int maxProfit = 0;
        // 遍历获得最大利润
        for (int i = 1; i < len; i++) {
            System.out.println("i为" + i + "时：" + dp[0][i - 1] + "_" + dp[i][len - 1]);
            maxProfit = Math.max(maxProfit, dp[0][i - 1] + dp[i][len - 1]);
        }

        maxProfit = Math.max(maxProfit, dp[0][len - 1]);

        return maxProfit;
    }

    public static int maxProfit2(int[] prices) {
        // 参数判断
        if (null == prices || prices.length < 2) {
            return 0;
        }

        int len = prices.length;
        // 定义dp数组，并初始化
        // left[i] 表示 前i+1天的最大利润
        int[] left = new int[len];
        left[0] = 0;
        // right[i]表示第i天之后的最大利润
        int[] right = new int[len];

        // left
        {
            int min = prices[0];
            for (int i = 1; i < len; i++) {
                if (prices[i] > min) {
                    left[i] = Math.max(left[i - 1], prices[i] - min);
                } else {
                    min = Math.min(min, prices[i]);
                }
            }
        }
        for (int num : left) {
            System.out.printf(num + "_");
        }
        System.out.println();

        // right
        for (int i = 1; i < len; i++) {
            int min = prices[i];
            // 记录此次循环的最利润
            int profit = 0;
            for (int j = i + 1; j < len; j++) {
                if (prices[j] > min) {
                    // 涨了，利润就会在之前的基础上增加
                    profit = Math.max(profit, prices[j] - min);
                } else {
                    // 没有涨，更新最小值
                    min = Math.min(min, prices[j]);
                }
            }
            right[i] = profit;
        }

        int maxProfit = 0;
        // 遍历获得最大利润
        for (int i = 1; i < len; i++) {
            maxProfit = Math.max(maxProfit, left[i - 1] + right[i]);
        }
        maxProfit = Math.max(maxProfit, left[len - 1]);
        return maxProfit;
    }

    /**
     * class Solution:
     * def maxProfit(self, prices):
     * if prices==[]:
     * return 0
     * length=len(prices)
     * #结束时的最高利润=[天数][是否持有股票][卖出次数]
     * dp=[ [[0,0,0],[0,0,0] ] for i in range(0,length) ]
     * #第一天休息
     * dp[0][0][0]=0
     * #第一天买入
     * dp[0][1][0]=-prices[0]
     * # 第一天不可能已经有卖出
     * dp[0][0][1] = float('-inf')
     * dp[0][0][2] = float('-inf')
     * #第一天不可能已经卖出
     * dp[0][1][1]=float('-inf')
     * dp[0][1][2]=float('-inf')
     * for i in range(1,length):
     * #未持股，未卖出过，说明从未进行过买卖
     * dp[i][0][0]=0
     * #未持股，卖出过1次，可能是今天卖的，可能是之前卖的
     * dp[i][0][1]=max(dp[i-1][1][0]+prices[i],dp[i-1][0][1])
     * #未持股，卖出过2次，可能是今天卖的，可能是之前卖的
     * dp[i][0][2]=max(dp[i-1][1][1]+prices[i],dp[i-1][0][2])
     * #持股，未卖出过，可能是今天买的，可能是之前买的
     * dp[i][1][0]=max(dp[i-1][0][0]-prices[i],dp[i-1][1][0])
     * #持股，卖出过1次，可能是今天买的，可能是之前买的
     * dp[i][1][1]=max(dp[i-1][0][1]-prices[i],dp[i-1][1][1])
     * #持股，卖出过2次，不可能
     * dp[i][1][2]=float('-inf')
     * return max(dp[length-1][0][1],dp[length-1][0][2],0)
     */
    public int maxProfit(int[] prices) {
        if (null == prices || prices.length < 2) {
            return 0;
        }
        int len = prices.length;
        int MIN_VALUE = Integer.MIN_VALUE / 2;
        // 定义dp数组，含义是结束时的最高利润=[天数][是否持有股票][卖出次数]
        int[][][] dp = new int[len][2][3];
        // 初始化第一天
        // 第一天什么都不做
        dp[0][0][0] = 0;
        // 第一天先买了股票
        dp[0][1][0] = -prices[0];
        // 这两种情况不存在
        dp[0][0][1] = dp[0][1][1] = MIN_VALUE;
        dp[0][0][2] = dp[0][1][2] = MIN_VALUE;
        for (int i = 1; i < len; i++) {
            // 前i天什么都没做
            dp[i][0][0] = 0;
            // 未持有状态，之前卖的或者，今天卖的
            dp[i][0][1] = Math.max(dp[i - 1][1][0] + prices[i], dp[i - 1][0][1]);
            dp[i][0][2] = Math.max(dp[i - 1][1][1] + prices[i], dp[i - 1][0][2]);
            // 买入状态，之前买的或者，今天买的
            dp[i][1][0] = Math.max(dp[i - 1][0][0] - prices[i], dp[i - 1][1][0]);
            dp[i][1][1] = Math.max(dp[i - 1][0][1] - prices[i], dp[i - 1][1][1]);
            dp[i][1][2] = MIN_VALUE;
        }

        // 只卖0次或一次或者两次
        return Math.max(0, Math.max(dp[prices.length - 1][0][1], dp[prices.length - 1][0][2]));
    }
}
